package leetcode

import kotlinetc.println

//https://leetcode.com/problems/word-search/

/**
Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring.
The same letter cell may not be used more than once.

Example:

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
 */
fun main(args: Array<String>) {

    val board = arrayOf(
            charArrayOf('A', 'B', 'C', 'E'),
            charArrayOf('S', 'F', 'C', 'S'),
            charArrayOf('A', 'D', 'E', 'E')
    )
    val board1 = arrayOf(
            charArrayOf('a', 'a')
    )
    exist(board1, "aaa").println()

}

fun exist(board: Array<CharArray>, word: String): Boolean {


    //起点可能有多个
    if (word.isEmpty()) return false

    val rows = board.size
    val cols = board[0].size

    val firstChar = word[0]
    for (i in 0 until rows)
        for (j in 0 until cols) {
            if (board[i][j] == firstChar) {
                val visited = Array(rows) {
                    Array(cols) { false }
                }
                visited[i][j] = true
                if (existWord(board, 0, i, j, visited, word))
                    return true

            }
        }
    return false

}

val dr = arrayOf(0, 0, 1, -1)
val dc = arrayOf(1, -1, 0, 0)

fun existWord(board: Array<CharArray>, index: Int, row: Int, col: Int, visited: Array<Array<Boolean>>, word: String): Boolean {


    if (index == word.lastIndex) return true


    var r = row - 1
    var c = col


    //four  if is too , for loop instead

    for (k in 0 until 4) {
        r = row + dr[k]
        c = col + dc[k]
        if (r in 0 until board.size && c in 0 until board[0].size && visited[r][c].not() && board[r][c] == word[index + 1]) {
            if (index + 1 == word.lastIndex)
                return true
            visited[r][c] = true
            if (existWord(board, index + 1, r, c, visited, word))
                return true
            else visited[r][c] = false
        }
    }

    return false

//
//    if (r >= 0 && visited[r][c].not() && board[r][c] == word[index + 1]) {
//        if (index + 1 == word.lastIndex)
//            return true
//        else {
//            visited[r][c] = true
//            if (existWord(board, index + 1, r, c, visited, word))
//                return true
//            else visited[r][c] = false
//        }
//    }
//
//
//    r = row
//    c = col + 1
//
//    if (c < board[0].size && visited[r][c].not() && board[r][c] == word[index + 1]) {
//
//        if (index + 1 == word.lastIndex)
//            return true
//        else {
//            visited[r][c] = true
//            if (existWord(board, index + 1, r, c, visited, word))
//                return true
//            else visited[r][c] = false
//
//        }
//    }
//
//
//
//    r = row + 1
//    c = col
//
//    if (r < board.size && visited[r][c].not() && board[r][c] == word[index + 1]) {
//        if (index + 1 == word.lastIndex)
//            return true
//        else {
//            visited[r][c] = true
//            if (existWord(board, index + 1, r, c, visited, word))
//                return true
//            else visited[r][c] = false
//
//        }
//    }
//
//
//
//    r = row
//    c = col - 1
//
//    if (c >= 0 && visited[r][c].not() && board[r][c] == word[index + 1]) {
//        if (index + 1 == word.lastIndex)
//            return true
//        else {
//            visited[r][c] = true
//            if (existWord(board, index + 1, r, c, visited, word))
//                return true
//            else visited[r][c] = false
//        }
//    }

//    return false

}
